package com.sali.DP;

/**
 * @author sali
 * @date 2025/5/4 16:16
 */
public class LeetCode_72 {

    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        for (int i1 = 0; i1 < word1.length() + 1; i1++) {
            dp[i1][0] = i1;
        }

        for (int i2 = 0; i2 < word2.length() + 1; i2++) {
            dp[0][i2] = i2;
        }

        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];

    }

}
